package app.engine;

import app.engine.component.TranspositionTable;
import app.engine.entitys.EvaluationTable;
import app.engine.entitys.Move;
import app.engine.component.AbstractSearchEngine;
import app.engine.enums.ItemType;
import app.game.ChessBoard;
import app.game.ChessPoint;
import app.game.enums.Chess;
import app.game.enums.Direction;
import sun.misc.Unsafe;

import java.util.Date;
import java.util.List;
import java.util.logging.Logger;


/**
 * @Description 搜索引擎实现
 * @Date 2022/4/18 21:18
 * @Created by LYP
 */
public class SearchEngine extends AbstractSearchEngine {

    public SearchEngine(){

    }

    Chess[][] sChessBoard;

    private void init(Chess[][] chessBoard) {
        sChessBoard = ChessBoard.copy(chessBoard);
    }

    private static final int MAX_DEPTH = 9;
    private static final int MAX_TIME = 15000;

    @Override
    public ChessPoint search(Chess[][] nowChessBoard, Chess comChess, int step, List<ChessPoint> stepHistory) {
        if (step == 1) {
            return new ChessPoint(BOARD_LINE / 2, BOARD_LINE / 2);
        }
        System.out.println("-----------------------------------------------------------------");
        Chess[][] chessBoard = ChessBoard.copy(nowChessBoard);
        System.out.println("人方走棋后局面评分:" + getValuation(chessBoard, comChess.getReverse()));
        ChessPoint chessPoint = rootSearch(nowChessBoard, comChess);
        chessBoard[chessPoint.getX()][chessPoint.getY()] = comChess;
        System.out.println("电脑走棋后局面评分:" + getValuation(chessBoard, comChess));
        return chessPoint;
    }

    private ChessPoint rootSearch(Chess[][] nowChessBoard, Chess nowChess) {
        init(nowChessBoard);
        List<Move> moves = getMoves(nowChessBoard, nowChess);
        moves.sort(Move::compareTo);
        Move bestMove = moves.get(0);
        int bestScore = EvaluationTable.MIN_SCORE;
        long startTime = new Date().getTime();
        // 初始化置换表
        transpositionTable.init(nowChessBoard);
        System.out.println("开始时间："+startTime);
        // 迭代加深搜索，直到搜索超时或者达到最大深度
        for (int maxDepth = 0; maxDepth < MAX_DEPTH; maxDepth++) {
            for (Move move: moves) {
                putChess(move, nowChess);
                transpositionTable.hashPutChess(move, nowChess);
                int score = -negaSearch(nowChess.getReverse(), EvaluationTable.MIN_SCORE, -bestScore, maxDepth);
                putBackChess(move);
                transpositionTable.hashPutBackChess(move);
                System.out.println("根节点走法是" + move.toString() + ",评分为" + score);
                if (score > bestScore) {
                    bestMove = move;
                    bestScore = score;
                }
            }
            long nowTime = new Date().getTime();
            System.out.println("第"+(maxDepth+1)+"次迭代，选择的最好走法是"+ bestMove.toString() + "，时间："+ (nowTime - startTime));
            if (nowTime - startTime > MAX_TIME) {
                break;
            }
            // 下次迭代时，先搜索最好招法（PV节点）
            if (maxDepth  < MAX_DEPTH - 1) {
                putBestToOne(moves, bestMove);
                bestMove = moves.get(0);
                bestScore = EvaluationTable.MIN_SCORE;
            }
        }
        System.out.println("选择的最好走法是" + bestMove.toString() + ",评分为" + bestScore);
        return new ChessPoint(bestMove.getX(), bestMove.getY());
    }

    /**
     * 负极大值搜索算法
     * @param nowChess 当前节点对应的行棋方
     * @param alpha 当前节点窗口的区间最小值
     * @param beta 当前节点窗口的区间最大值
     * @param depth 当前节点深度
     * @return
     */
    private int negaSearch(Chess nowChess, int alpha, int beta, int depth) {
        // 如果置换表搜索到，直接返回分值
        int ttScore = transpositionTable.searchHashTable(alpha, beta, depth);
        if (ttScore != TranspositionTable.NOT_HIT) {
            return ttScore;
        }
        // 如果已经终局，则直接返回最大值
        if (isEnd(nowChess.getReverse())) {
            return -EvaluationTable.MAX_SCORE;
        }
        // 如果是叶子节点，则直接返回评分，注意是相对于上一层节点行棋方的分数
        if (depth == 0) {
            int score = -getValuation(sChessBoard, nowChess.getReverse());
            transpositionTable.insertHashTable(ItemType.EXACT, score, depth);
            return score;
        }
        List<Move> moves = getMoves(sChessBoard, nowChess);
        moves.sort(Move::compareTo);
        int bestScore = EvaluationTable.MIN_SCORE;
        ItemType itemType = ItemType.UPPERBOUND;
        for (Move move: moves) {
            putChess(move, nowChess);
            transpositionTable.hashPutChess(move, nowChess);
            int score = -negaSearch(nowChess.getReverse(), -beta, -alpha, depth - 1);
            putBackChess(move);
            transpositionTable.hashPutBackChess(move);
            //System.out.println(depth + "层节点走法是" + move.toString() + ",评分为" + score);
            if (score > bestScore) {
                bestScore = score;
                // 更新alpha
                if (score > alpha) {
                    alpha = score;
                    itemType = ItemType.EXACT;
                    //System.out.println("更新窗口为["+alpha+","+beta+"]");
                }
            }
            // 当alpha大于beta值，说明窗口已经无效，需要剪枝
            if (alpha > beta) {
                itemType = ItemType.LOWBOUND;
                //System.out.println("窗口["+alpha+","+beta+"]发生剪枝！");
                break;
            }
        }
        transpositionTable.insertHashTable(itemType, bestScore, depth);
        return bestScore;
    }

    private void putChess(Move move, Chess nowChess) {
        sChessBoard[move.getX()][move.getY()] = nowChess;
    }

    private void putBackChess(Move move) {
        sChessBoard[move.getX()][move.getY()] = Chess.EMPTY;
    }

    private void putBestToOne(List<Move> moves, Move bestMove) {
        int bestIndex = 0;
        for (int i = 0; i < moves.size(); i++) {
            if (moves.get(i).equals(bestMove)) {
                bestIndex = i;
                break;
            }
        }
        Move temp = moves.get(bestIndex);
        moves.set(bestIndex, moves.get(0));
        moves.set(0, temp);
    }

    public boolean isEnd(Chess nowChess){
        for (int i = 0; i < BOARD_LINE; i++) {
            for (int j = 0; j < BOARD_LINE; j++) {
                if (sChessBoard[i][j] == nowChess) {
                    ChessPoint thisPoint = new ChessPoint(i, j);
                    Direction[] directions = Direction.values();
                    for (Direction direction: directions) {
                        int count = 1;
                        ChessPoint point = thisPoint.getNext(direction, 1);
                        while (point.isOnTable() && sChessBoard[point.getX()][point.getY()] == nowChess) {
                            count++;
                            point.next(direction, 1);
                        }
                        point = thisPoint.getNext(direction, -1);
                        while (point.isOnTable() && sChessBoard[point.getX()][point.getY()] == nowChess) {
                            count++;
                            point.next(direction, -1);
                        }
                        if (count >= 5) {
                            return true;
                        }
                    }
                }

            }
        }

        return false;
    }

}
